/*
 * @Author: scl
 * @Date: 2023-08-15 16:11:17
 * @LastEditTime: 2023-08-16 23:30:06
 * @Description: file content
 */
/*
 * @lc app=leetcode.cn id=108 lang=typescript
 *
 * [108] 将有序数组转换为二叉搜索树
 *
 * https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
 *
 * algorithms
 * Easy (77.51%)
 * Likes:    1363
 * Dislikes: 0
 * Total Accepted:    378K
 * Total Submissions: 487.5K
 * Testcase Example:  '[-10,-3,0,5,9]'
 *
 * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
 * 
 * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [-10,-3,0,5,9]
 * 输出：[0,-3,9,-10,null,5]
 * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
 * 
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [1,3]
 * 输出：[3,1]
 * 解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= nums.length <= 10^4
 * -10^4 <= nums[i] <= 10^4
 * nums 按 严格递增 顺序排列
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 *  class TreeNode {
 *      val: number
 *      left: TreeNode | null
 *      right: TreeNode | null
 *      constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *          this.val = (val===undefined ? 0 : val)
 *          this.left = (left===undefined ? null : left)
 *          this.right = (right===undefined ? null : right)
 *      }
 *  }
 */

function sortedArrayToBST(nums: number[]): TreeNode | null {
    const m:number=nums.length,mid=~~(m/2), head=new TreeNode(nums[mid]),nodeArr:TreeNode[]=[]
    if (m == 1) return head
    else {
        let i = mid - 1
        const nodeL1 = new TreeNode(nums[i],null,null),nodeR1=new TreeNode(nums[m-1],null,null)
        head.left=nodeL1
        head.right=nodeR1
        nodeArr.push(nodeR1,nodeL1)
        i--
        while (i >= 0) {
            const node=nodeArr.pop(),nodeL=new TreeNode(nums[i])
            node.left = nodeL
            i--
            if (i >= 0) {
                const nodeR = new TreeNode(nums[i],null,null)
                node.right = nodeR
                nodeArr.push(nodeL, nodeR)
                i--
            }
        }
        i = m-2
        nodeArr.length = 1
        while (i > mid) {
            const node = nodeArr.pop(), nodeL = new TreeNode(nums[i],null,null)
            node.left = nodeL
            i--
            if (i > m) {
                const nodeR = new TreeNode(nums[i],null,null)
                node.right = nodeR
                nodeArr.push(nodeL, nodeR)
                i--
            }
        }
    }
    return head;
};
// @lc code=end

